package PX.插入排序;

import java.util.Arrays;

public class Insert_sort {
    public static void main(String[] args) {
        //测试一把
        int[] arr = new int[]{100,-1,2,1,20,13,12};
        int[] ints = insert_sort(arr);
        System.out.println(Arrays.toString(ints));
    }

    public static int[] insert_sort(int[] arr) {
        if (arr.length == 0){
            return arr;
        }
        int insert;//待比较的数据  默认从arr[i]下一个开始
        for (int i = 0; i < arr.length - 1; i++) {
            insert = arr[i+1];
            int preIndex = i;//定义一个开始比较的起点
            //preIndex >= 0  保证不越界
            //insert < arr[preIndex] 我小就是我前进的动力
            while(preIndex >= 0 &&insert < arr[preIndex]){
                arr[preIndex + 1] = arr[preIndex];//插入的时候所有下标往后挪一个
                //多了一个分身，多了一个位置
                preIndex--;
            }
            arr[preIndex+1] = insert;//弹出来就是到了该插入的地方了
        }
        return arr;
    }



}
